package gold.digger;

import gold.utils.InputUtil;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC1765 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public int[][] highestPeak(int[][] g) {
            int m = g.length, n = g[0].length;
            int[][] ans = new int[m][n];
            Deque<int[]> d = new ArrayDeque<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    // 水域作为起点入队
                    if (g[i][j] == 1) d.addLast(new int[]{i, j});
                    // 没被访问过的陆地起始为-1，水域在答案里要求为0
                    ans[i][j] = g[i][j] == 1 ? 0 : -1;
                }
            }
            int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
            // 初始高度（和水域相邻的点最高只能为1）
            int h = 1;
            while (!d.isEmpty()) {
                // 当前队列的大小，因为遍历中要往队列里添加元素（下一层），这样写是必要的（避免当前层和下一层的遍历混淆）
                int size = d.size();
                while (size-- > 0) {
                    int[] info = d.pollFirst();
                    int x = info[0], y = info[1];
                    for (int[] di : dirs) {
                        int nx = x + di[0], ny = y + di[1];
                        // 下一个点出界了
                        if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                        // 下一个点被访问过了
                        if (ans[nx][ny] != -1) continue;
                        // 目前是bfs到nx，ny这个点最近的方式了，也就是该点最高的高度
                        ans[nx][ny] = h;
                        // 作为下一层遍历的元素入队
                        d.addLast(new int[]{nx, ny});
                    }
                }
                // 陆地高度逐级累加
                h++;
            }
            return ans;
        }
    }

    public void run() {
        Solution solution = new Solution();
        int[] arr = InputUtil.toIntegerArray("[1,2,3]");
        System.out.println(solution.toString());
    }

    public static void main(String[] args) throws Exception {
        LC1765 an = new LC1765();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
